package backtrackingalgorithm;

import jdk.jfr.StackTrace;
import org.junit.Test;

/**
 * @author DuJiabao
 * @create 2021-01-01 23:07
 * 我们有一个 8x8 的棋盘，希望往里放 8 个棋子（皇后），每个棋子所在的行、列、对角线都不能有另一个棋子。
 */
public class EightQueens {
    int result[] = new int[8]; //保存每行在第几列有
    int count = 0;
    private void calQueen(int row) {
        if (row == 8) {
            count++;
            printQueens();
            return;
        }
        for (int col = 0; col < 8; col++) {
            if (isOK(row, col)) {
                result[row] = col;
                calQueen(row + 1);
            }
        }
    }

    private boolean isOK(int row, int col) {
        int leftUp = col - 1;
        int rightUp = col + 1;
        for (int i = row - 1; i >= 0; i--) {
            if (result[i] == col) return false;
            if (leftUp >= 0 && result[i] == leftUp) return false;
            if (rightUp < 8 && result[i] == rightUp) return false;
            leftUp--;
            rightUp++;
        }
        return true;
    }

    private void printQueens() {
        for (int i : result) {
            for (int j = 0; j < i; j++) {
                System.out.print("* ");
            }
            System.out.print("Q ");
            for (int j = 0; j < 8 - i - 1; j++) {
                System.out.print("* ");
            }
            System.out.println();
        }
        System.out.println();
    }

    @Test
    public void test() {
        calQueen(0);
        System.out.println(count); //92种
    }

}
